The present invention relates to decoding of digital information sequences and in particular to Viterbi decoding of encrypted digital information sequences.
A typical communication scheme includes a transmitter, with a modulator for converting a digital information sequence into a signal, and a receiver, with a demodulator which can recover a digital information sequence from the received signal. A channel, which is between a transmitter and a receiver and may be wireless or wireline, may degrade the signal, through attenuation or the introduction of noise, such that a received sequence differs from the transmitted sequence. The differences between the transmitted and received sequences may be called xe2x80x9cerrorsxe2x80x9d. To minimize errors in received sequences, forward error correction coding may be employed through the use of a channel encoder in the transmitter and a channel decoder in the receiver.
Error correction coding is the practice of transmitting additional redundant bits besides the digital information sequence such that a receiver may determine if the received sequence is the same as the sent sequence and, if not, correct the received sequence. The coding may be applied intermittently to xe2x80x9cblocksxe2x80x9d of bits, continuously to bits in a bit stream or employ a combination of the two methods. One form of continuous coding is xe2x80x9cconvolutional codingxe2x80x9d in which a series of bits at the output of a channel encoder represent a result of operations performed on a set number of input bits. In a rate xc2xd convolutional encoder, a series of two new output bits are generated for each input bit. Along with the rate of a convolutional encoder, another characteristic is a constraint length. The constraint length indicates the number of inputs that are operated upon to generate each output. A rate xc2xd convolutional encoder which outputs two bits v1 and v2 for each input ut has a xe2x80x9cconstraint lengthxe2x80x9d of 3 if bits v1 and v2 are based on operations performed on ut and the two bits previous to ut, ut-1 and ut-2. For example, we could have v1=ut+ut-1+ut-2 and v2=ut+ut-2, where xe2x80x9c+xe2x80x9d represents modulo-2 addition.
A digital information sequence which has been subject to error correction coding must be decoded at the receiver. An optimum maximum likelihood decoder, for this type of coding, determines a sequence of bits which has a maximum likelihood of being the sequence that was sent. The Viterbi algorithm is a maximum likelihood decoding scheme for use at a receiver where an information sequence has employed an encoder using convolutional codes and the channel is an additive white Gaussian noise channel.
In general, channel decoding can be performed in two ways, namely, hard-decision decoding in a hard bit domain and soft-decision decoding in a soft bit (symbol) domain. Usually, samples of the demodulated signal are quantized resulting in bits so that, at the output of a demodulator, decoding can be performed in a bit-wise manner. In the hard bit domain, the demodulator quantizes each sample to one of two levels, i.e. 0 or 1, and is said to have made a hard-decision. The decoder that works with this kind of input is said to perform hard-decision decoding. On the other hand, if quantization is performed using more than two levels per bit, the resulting quantized samples are called soft symbols, or simply, symbols. The decoder making use of the information in soft-symbols is performing soft-decision decoding.
Hard-decision decoding has the advantage of less computational complexity than soft-decision decoding due to binary bit-wise operation. However, some useful information is lost during quantization. Therefore, hard-decision decoding does not perform very well under certain circumstances including, for example, a distorted channel, which is the case for real wireless communication systems.
A soft-decision decoder receives soft-decision inputs, which makes it more complex to implement. However, soft-decision decoding offers significantly better performance than hard-decision decoding. It has been reported that, to achieve the same error probability, at least 2 dB more signal power must be generated at the transmitter when the demodulator provides a hard-decision output, assuming an Additive White Gaussian Noise (AWGN) channel (see, for example, S. Lin and D. J. Costello Jr., xe2x80x9cError Control Coding: Fundamentals and Applicationsxe2x80x9d, Prentice-Hall, 1983, which is incorporated herein by reference). In other words, there is a 2 dB or more improvement for soft-decision decoding in an AWGN channel. In addition, this improvement implies an increment of the capacity in a cellular system, an important issue in the wireless industry.
U.S. Pat. No. 5,802,116 issued Sep. 1, 1998 to Baker et al. presents a method and apparatus for obtaining a soft symbol decoded output of a received signal by a two pass Viterbi operation. In a first pass the received signal is hard decision decoded. In a second pass the received signal is soft decision decoded with previously decoded hard bit information used as a most likely next state at a given time instant. This method sacrifices time in order to conserve memory required to store all possible next states at a given time instant.
A soft decision decoding receiver is disclosed in U.S. Pat. No. 5,844,946 issued Dec. 1, 1998 to Nagayasu. Used to reduce errors in channels which causes intersymbol interference (ISI), the receiver uses a training sequence to estimate the ISI present and uses the estimation to derive a replica of a received signal. The actual received signal and the replica are compared to generate a local metric for a particular path from a state at one time instant to a next state. The local metric is then used in a maximum likelihood decoding algorithm such as the Viterbi algorithm to obtain a decoded bit sequence.
The above patents are but two of a large volume of patents related to channel decoding. It should be noted that neither contemplate using soft decision decoding in conjunction with encryption.
In cellular telephony, the channel is a wireless connection from a mobile telephone to a relatively nearby base station. Despite channel coding, a properly equipped individual may xe2x80x9clisten inxe2x80x9d to conversations taking place over the channel. For this reason, a digital representation of a voice message may be encrypted.
Encryption in cellular telephony has drawn attention recently due to an increased requirement for personal privacy, electronic commerce and prevention of cellular phone fraud. Standards for digital mobile telephony were developed to include voice ciphering and signalling message and data encryption (see, for example, Electronics Industries Association/Telecommunication Industries Association (EIA/TIA) Interim Standard 95 (IS-95) for Code Division Multiple Access (CDMA) and Interim Standard (IS-136) for Time Division Multiple Access (TDMA)). In IS-136, encryption is applied after error correction coding of the speech signal and before modulation.
In a typical communication scheme, an encryption operation is performed before modulation in the transmitter and a decryption operation is performed after demodulation in the receiver. Current encryption schemes depend on this placement as encryption and decryption are performed in a binary bit-wise manner. For example, an encryption operation could comprise performing an exclusive-OR (XOR) operation with an encryption mask and the encoded information sequence as operands. The following is a truth table for the XOR (⊕) operation.
If soft-decision decoding is used in the receiver, the input to the soft-decision decoder must be soft-decision samples instead of binary bits. This requires the demodulator make a soft-decision to obtain output symbols, for example, a multi-level quantized real number, 0.75, or a complex number, exp(j3xcfx80/8). As a result, the input and output of the decryption process may be in soft symbol format. As discussed, current encryption schemes are based on an operation on binary bits.
One possible way of combining soft-decision decoding and XOR-based decryption is to map the bit-wise encryption mask and XOR operation into the symbol domain. This mapping not only makes soft-decision decoding possible under current practice in IS-136 but also provides a technique that can map the XOR-based bit operation into the symbol domain in a communication system using phase-shift keying (PSK). However, the above method can only achieve optimum results when the modulation level is low, namely 2 or 4 PSK (see, for instance, application Ser. No. 08/953,763, xe2x80x9cSystem and Method for Decryption in the Symbol Domainxe2x80x9d, Karl Mann and Yan Hui, hereby incorporated by reference). While this is sufficient for such communication systems as IS-136 TDMA systems, it cannot provide an optimum solution for higher level modulation, 8 PSK, for example, which has been standardized in IS-136 Rev. B, GPRS-136 and EDGE.
A method is provided for embedding decryption into Viterbi decoding. Metrics associated with paths of a Viterbi decoding trellis are calculated from a received signal and an encrypted path state. When the method is used in conjunction with a communication channel, such as the AWGN channel, where the received signal and encrypted path state are in the symbol domain, significantly less transmitter power is required than is required when encryption and decoding are performed separately in a hard bit domain.
In accordance with an aspect of the present invention there is provided a method for use in channel decoding including obtaining a channel decoding trellis having states, stages, and paths between states of adjacent stages, each of the paths having an associated path state. The method further including encrypting each path state with an encryption mask to result in an encrypted path state.
In accordance with another aspect of the present invention there is provided, in a channel decoding trellis comprising states and paths between the states, a method for selecting one path from a plurality of paths leading to a destination state. The method includes, for each path of the plurality of paths leading to the destination state, encrypting a path state, associated with each path, with an encryption mask to result in an encrypted path state, calculating a local metric from an input and the encrypted path state and associating the local metric with each path. Also for each path, the method includes associating an overall path metric with each path, where the overall path metric is equivalent to a sum of the local metric and an overall state metric associated with a state at the origin of the path. The method concludes by selecting one path of the plurality of paths leading to the destination state based at least in part on each overall path metric. In accordance with further aspects of the present invention there is provided a decoder having a processor for carrying out this method of the present invention, a communication system including a decoder having a processor for carrying out this method of the present invention and a computer software medium for providing program control for a processor for carrying out this method of the present invention.
In accordance with another aspect of the present invention there is provided a method for use in decrypting and decoding encrypted coded soft symbols, including associating a given encrypted encoded soft symbol with at least one stage and state of a decoding trellis, each path of the decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state. The method further includes obtaining an encryption mask for use in decrypting the given encrypted encoded soft symbol, encrypting the equivalent hard symbol path state in the decoding trellis associated with each path leading to the at least one stage and state, utilising said encryption mask and determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state. The method concludes by determining metrics, each based on the given encrypted encoded soft symbol and one encrypted soft symbol path state. In accordance with a further aspect of the present invention there is provided a decoder for carrying out this method of the present invention.
In accordance with another aspect of the present invention there is provided a method for use in decrypting and decoding encrypted coded symbols, including associating a given encrypted encoded symbol with at least one stage and state of a decoding trellis, each path of the decoding trellis having an associated symbol path state which, where the trellis is in a hard symbol domain, is a hard symbol path state and which, where the trellis is in a soft symbol domain, is a soft symbol path state with an equivalent hard symbol path state. The method further includes obtaining an encryption mask for use in decrypting the given encrypted encoded symbol, encrypting said hard symbol path state in said decoding trellis associated with each path leading to said at least one stage and state, utilising said encryption mask. The method concludes by determining metrics utilising the given encrypted encoded symbol and each encrypted hard symbol path state. In accordance with a further aspect of the present invention there is provided a decoder for carrying out this method of the present invention.
In accordance with another aspect of the present invention there is provided a method for use in a decoder, including, obtaining an encryption mask. The method further includes, in a decoding trellis having an associated soft symbol path state and an equivalent hard symbol path state, determining a destination state corresponding with said encryption mask and encrypting the equivalent hard symbol path state associated with each path leading to the destination state utilising the encryption mask. The method concludes by determining an encrypted soft symbol path state corresponding to each encrypted equivalent hard symbol path state. In accordance with a further aspect of the present invention there is provided a decoder for carrying out this method of the present invention.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.